package zhengqc.tree;

import zhengqc.list.List;
import zhengqc.queue.LoopQueue;
import zhengqc.queue.Queue;

public abstract class AbstractBSTree<E extends Comparable<E>> {
    class Node {
        public Node left;
        public E element;
        public Node right;
        public int height;
        public Node(Node left, E element, Node right, int height) {
            this.left = left;
            this.element = element;
            this.right = right;
            this.height = height;
        }
        public Node(E element) {
            this(null, element, null, 1);
        }
    }

    protected Node root;
    protected int size;
    protected List<E> tempList;
    protected E tempElement;

    /* 清空二叉树 */
    public void clear() {
        this.root = null;
        this.size = 0;
    }
    /* 判断二叉树是否为空 */
    public boolean isEmpty() {
        return this.size == 0;
    }
    /* 二叉树节点的数量 */
    public int getSize() {
        return size;
    }
    /* 在以 node 为根的二分搜索树中查找值为 element 的节点 */
    protected boolean contains(Node node, E element) {
        if (node == null) {
            return false;
        }
        if (element.compareTo(node.element) < 0) {
            return contains(node.left, element);
        } else if (element.compareTo(node.element) > 0) {
            return contains(node.right, element);
        } else {
            return true;
        }
    }
    /* 二叉树中是否含有指定的元素 */
    public boolean contains(E element) {
        return contains(this.root, element);
    }
    /* 判断二叉树是否为二分搜索树 */
    public boolean isBSTree() {
        this.tempList.clear();
        inorder(this.root);
        int size = tempList.getSize();
        for (int i = 1; i < size; ++i) {
            if ( tempList.get(i-1).compareTo(tempList.get(i)) > 0 ) {
                return false;
            }
        }
        return true;
    }
    /* 判断以 node 为根的二叉树是否为平衡二叉树 */
    protected boolean isBalanced(Node node) {
        if (node == null) {
            return true;
        }
        // 计算平衡因子
        int balanceFactor = getBalanceFactor(node);
        if (Math.abs(balanceFactor) > 1) {
            return false;
        }
        return isBalanced(node.left) && isBalanced(node.right);
    }
    /* 判断二叉树是否为平衡二叉树 */
    public boolean isBalanced() {
        return isBalanced(this.root);
    }
    /* 先序遍历 */
    protected void preorder(Node node) {
        if (node == null) {
            return;
        }
        this.tempList.addLast(node.element);
        preorder(node.left);
        preorder(node.right);
    }
    /* 中序遍历 */
    protected void inorder(Node node) {
        if (node == null) {
            return;
        }
        inorder(node.left);
        this.tempList.addLast(node.element);
        inorder(node.right);
    }
    /* 后序遍历 */
    protected void postorder(Node node) {
        if (node == null) {
            return;
        }
        postorder(node.left);
        postorder(node.right);
        this.tempList.addLast(node.element);
    }
    /* 层序遍历 */
    protected void level(Node node) {
        Queue<Node> queue = new LoopQueue<>();
        queue.enqueue(node);
        while (!queue.isEmpty()) {
            Node current = queue.dequeue();
            this.tempList.addLast(current.element);
            if (current.left != null) {
                queue.enqueue(current.left);
            }
            if (current.right != null) {
                queue.enqueue(current.right);
            }
        }
    }
    /* 遍历二叉树 */
    public List<E> traversal(TreeTraversalType traversal_type) {
        this.tempList.clear();
        switch (traversal_type) {
            case PREORDER:
                preorder(this.root);
                break;
            case INORDER:
                inorder(this.root);
                break;
            case POSTORDER:
                postorder(this.root);
                break;
            case LEVELORDER:
                level(this.root);
        }
        return this.tempList;
    }

    /* 返回以 node 为根的二分搜索树中值为 element 的节点 */
    protected Node getNode(Node node, E element) {
        if (node == null) {
            return null;
        }
        if (element.compareTo(node.element) < 0) {
            return getNode(node.left, element);
        } else if (element.compareTo(node.element) > 0) {
            return getNode(node.right, element);
        } else {
            return node;
        }
    }
    /* 从二叉树中获取指定元素; 原则上不需要此方法, 仅供特殊需求, 如实现 Map */
    public E get(E element) {
        Node node = getNode(this.root, element);
        return (node==null) ? null : node.element;
    }
    /* 返回以 node 为根节点的二分搜索树的最小节点 */
    protected Node getMinimumNode(Node node) {
        if (node.left == null) {
            return node;
        }
        return getMinimumNode(node.left);
    }
    /* 获取二叉树最小的元素 */
    public E getMinimum() {
        Node node = getMinimumNode(this.root);
        return node.element;
    }
    /* 返回以 node 为根节点的二分搜索树的最大节点 */
    protected Node getMaximumNode(Node node) {
        if (node.right == null) {
            return node;
        }
        return getMaximumNode(node.right);
    }
    /* 获取二叉树最大的元素 */
    public E getMaximum() {
        Node node = getMaximumNode(this.root);
        return node.element;
    }
    /* 获取以 node 为根树的高度 */
    protected int getHeight(Node node) {
        if (node == null) {
            return 0;
        }
        return node.height;
    }
    /* 获取以 node 的平衡因子 */
    protected int getBalanceFactor(Node node) {
        if (node == null) {
            return 0;
        }
        return getHeight(node.left) - getHeight(node.right);
    }

    /* 向二分搜索树插入元素 */
    public void add(E element) {}

    /* 从二分搜索树中删除指定元素; 原则上不需要返回值, 仅供特殊需求, 如实现 Map */
    public E remove(E element) { return null; }

    /* 删除二分搜索树中最大的元素, 并返回 */
    public E removeMaximum() { return null; }

    /* 删除二分搜索树中最小的元素, 并返回 */
    public E removeMinimum() { return null; }
}
